#define elif else if
#include<bits/stdc++.h>
#include"heap.cpp"
#include"DisjointSetUnion.cpp"
using namespace std;
int* D;
struct Comp
{
	static bool prior(int a,int b)
	{
		return D[a]<D[b];
	}
};
int main()
{
	int n,e,start;
	while(cin>>n>>e>>start)
	{
		D=new int[n];
		bool*visited=new bool[n];
		vector< vector<int> >edge;
		int**input=new int*[e];
		for(int i=0;i<e;i++)input[i]=new int[2];
		int*V=new int[n];
		heap<int,Comp>minheap;
		minheap.insert(start);
		for(int i=0;i<n;i++)
		{
			D[i]=INT_MAX;
			visited[i]=false;
			V[i]=INT_MAX;
			edge.push_back(vector<int>());
			for(int j=0;j<n;j++)edge[i].push_back(INT_MAX);
		}
		D[start]=0;V[start]=start;
		for(int i=0;i<e;i++)
		{
			int weight=0;
			cin>>input[i][0]>>input[i][1]>>weight;
			edge[input[i][0]][input[i][1]]=weight;
			edge[input[i][1]][input[i][0]]=weight;
		}
		for(int i=0;i<n-1;i++)
		{
			int ss=minheap.removefirst();
			while(visited[ss])ss=minheap.removefirst();
			if(D[ss]==INT_MAX)return 0;
			visited[ss]=true;
			for(int p=0;p<n;p++)
			{
				if(edge[ss][p]!=INT_MAX&&D[p]>edge[ss][p])
				{
					D[p]=edge[ss][p];
					if(V[p]==INT_MAX)V[p]=ss;
					minheap.insert(p);
				}
			}
		}
		for(int i=0;i<n;i++)cout<<D[i]<<" ";cout<<endl;
		for(int y=0;y<n;y++)cout<<V[y]<<" ";cout<<endl;
		system("pause");
	}
}
				
//测试数据：第一行为点数、边数、出发点
//以下数据可直接去除注释复制粘贴使用
//其余每行为各点之间的边及其权重
//warning：出发点的输入需要其之间有通路
// 6 8 2
// 0 2 7
// 0 4 9
// 1 2 5
// 2 3 1
// 2 5 2
// 3 5 2
// 1 5 6
// 4 5 1